/**
 * https://leetcode.cn/submissions/detail/577643537/
 * 面试题 17.06. 2出现的次数
 * Hard, 黄伟杰 2024.10.05
 * 数位DP
 */

#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    int numberOf2sInRange(int n)
    {
        string s = to_string(n);
        int m = s.length(), dp[m][m];
        memset(dp, -1, sizeof(dp));
        auto dfs = [&](auto &&dfs, int i, int cnt, bool is_limit) -> int
        {
            if (i == m)
            {
                return cnt;
            }
            if (!is_limit && dp[i][cnt] != -1)
            {
                return dp[i][cnt]; // 之前计算过
            }
            int res = 0;
            // 上限
            int up = is_limit ? s[i] - '0' : 9;
            // 枚举要填入的数字 d
            for (int d = 0; d <= up; d++)
            {
                res += dfs(dfs, i + 1, cnt + (d == 2), is_limit && d == up);
            }
            if (!is_limit)
            {
                dp[i][cnt] = res; // 记忆化
            }
            return res;
        };
        return dfs(dfs, 0, 0, true);
    }
};